package org.zhixiang.gisQuery.utils;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

/**
 * histogram图形法
 * 
 * @say little Boy, don't be sad.
 * @name Rezar
 * @time 2018年9月25日 上午10:35:31
 * @Desc 些年若许,不负芳华.
 *
 */
public class JuXingMaxRect {

	public static void main(String[] args) {
		Integer[][] build = build();
		findMaxArea(build);
		System.out.println("=============");
		findMaxArea1(build);
	}

	/**
	 * 
	 */
	public static void findMaxArea1(Integer[][] originData) {
		Integer[][] newArray = rebuild(originData);
		List<Integer> area = new ArrayList<Integer>();
		for (int i = 0; i < newArray.length; i++) {
			Integer temp = countArea(newArray[i]);
			area.add(temp);
		}
		System.out.println(Collections.max(area));
	}

	public static AreaNodeRecord findMaxArea(Integer[][] originData) {
		Integer[][] newArray = rebuild(originData);
		List<AreaNodeRecord> areas = new ArrayList<>();
		for (int i = 0; i < newArray.length; i++) {
			AreaNodeRecord countArea = countArea2(newArray[i], i);
			areas.add(countArea);
		}
		Collections.sort(areas);
		AreaNodeRecord areaNodeRecord = areas.get(0);
		return areaNodeRecord;
	}

	public static List<AreaNodeRecord> findAllMaxArea(Integer[][] originData) {
		Integer[][] newArray = rebuild(originData);
		List<AreaNodeRecord> areas = new ArrayList<>();
		for (int i = 0; i < newArray.length; i++) {
			AreaNodeRecord countArea = countArea2(newArray[i], i);
			areas.add(countArea);
		}
		Collections.sort(areas);
		return areas;
	}

	// 接收控制台输入的二维数组
	public static Integer[][] build() {
		Scanner in = new Scanner(System.in);
		int row = in.nextInt();
		int column = in.nextInt();
		Integer[][] array = new Integer[row][column];
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < column; j++) {
				array[i][j] = in.nextInt();
			}
		}
		in.close();
		return array;
	}

	// 重构二维数组，变成histogram类型。
	public static Integer[][] rebuild(Integer[][] array) {
		Integer[][] newArray = new Integer[array.length][array[0].length];
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array[0].length; j++) {
				int height = 0;
				for (int k = i; k < array.length; k++) {
					if (array[k][j] == 1) {
						height += 1;
					} else {
						break;
					}
				}
				newArray[i][j] = height;
			}
		}
		return newArray;
	}

	// histogram图形法：
	public static int countArea(Integer[] array) {
		Stack<Node> stack = new Stack<Node>();
		stack.push(new Node(0, 0));
		List<Integer> list = new ArrayList<Integer>();

		// 扫面
		for (int i = 0; i <= array.length; i++) {
			// 当将所有元素有扫了一遍之后，需要将栈堆弹空，并计算每一个矩形的面积
			if (i == array.length) {
				// 判断是否弹到第一个元素(0,0),是的话就结束，返回最大面积。
				while (stack.peek().getStartIndex() != 0) {
					Integer area = (i + 1 - stack.peek().getStartIndex()) * stack.peek().getHeight();
					list.add(area);
					stack.pop();
				}
				return Collections.max(list);
			}
			// 新的元素比前一个元素的高度高，则入栈
			if (array[i] >= stack.peek().getHeight()) {
				stack.push(new Node(array[i], i + 1));
			} else {
				int index = 0;
				// 新的元素比前一个元素的高度高，则计算当前矩形的面积，并出栈
				while (array[i] < stack.peek().getHeight()) {
					Integer area = (i + 1 - stack.peek().getStartIndex()) * stack.peek().getHeight();
					list.add(area);
					index = stack.peek().getStartIndex();
					stack.pop();
				}
				// 将新的元素入栈
				stack.push(new Node(array[i], index));
			}
		}
		return 0;
	}

	public static AreaNodeRecord countArea2(Integer[] array, int originLevel) {
		Stack<Node> stack = new Stack<Node>();
		stack.push(new Node(0, 0));
		List<AreaNodeRecord> areaNodeRecordList = new ArrayList<>();
		// 扫面
		for (int i = 0; i <= array.length; i++) {
			// 当将所有元素有扫了一遍之后，需要将栈堆弹空，并计算每一个矩形的面积
			if (i == array.length) {
				// 判断是否弹到第一个元素(0,0),是的话就结束，返回最大面积。
				while (stack.peek().getStartIndex() != 0) {
					Integer area = (i + 1 - stack.peek().getStartIndex()) * stack.peek().getHeight();
					areaNodeRecordList.add(new AreaNodeRecord(originLevel, area, stack.peek().getStartIndex(),
							stack.peek().getHeight()));
					stack.pop();
				}
				Collections.sort(areaNodeRecordList);
				return areaNodeRecordList.get(0);
			}
			// 新的元素比前一个元素的高度高，则入栈
			if (array[i] >= stack.peek().getHeight()) {
				stack.push(new Node(array[i], i + 1));
			} else {
				int index = 0;
				// 新的元素比前一个元素的高度高，则计算当前矩形的面积，并出栈
				while (array[i] < stack.peek().getHeight()) {
					Integer area = (i + 1 - stack.peek().getStartIndex()) * stack.peek().getHeight();
					areaNodeRecordList.add(new AreaNodeRecord(originLevel, area, stack.peek().getStartIndex(),
							stack.peek().getHeight()));
					index = stack.peek().getStartIndex();
					stack.pop();
				}
				// 将新的元素入栈
				stack.push(new Node(array[i], index));
			}
		}
		return null;
	}
}

// 节点
class Node {
	// 矩形高度
	Integer height;
	// 矩形坐标
	Integer startIndex;

	Node(Integer height, Integer startIndex) {
		this.height = height;
		this.startIndex = startIndex;
	}

	public Integer getHeight() {
		return height;
	}

	public void setHeight(Integer height) {
		this.height = height;
	}

	public Integer getStartIndex() {
		return startIndex;
	}

	public void setStartIndex(Integer startIndex) {
		this.startIndex = startIndex;
	}
}
